package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description leetcode 213. 打家劫舍 II
 * @date 2025/10/20 17:19
 */
public class E213 {

    /**
     * <p>思路，考虑数组头和数组尾，分成三种情况：</p>
     * <ol>
     *  <li>选择head不选tail</li>
     *  <li>不选head选择tail</li>
     *  <li>不选head不选tail</li>
     * </ol>
     * <p>分别统计三种情况下的最优值，每种情况采用动态规划，</p>
     * <p>最后取三种情况的最大值，</p>
     *
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        // 1. 处理1和2的情况
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        int tail = nums.length - 1;
        // 2. 按头和尾的情况分三类
        int r = Math.max(rob(nums, 2, tail - 1) + nums[0], rob(nums, 1, tail - 2) + nums[tail]);
        return Math.max(r, rob(nums, 1, tail - 1));
    }

    /**
     * <p>动态规划，</p>
     * <p>dp[i] 表示从begin到i的数组的最优解</p>
     *
     * @param nums  数组
     * @param begin 开始索引
     * @param end   结束索引
     * @return 最优值
     */
    private int rob(int[] nums, int begin, int end) {
        if (begin > end) return 0;
        int[] dp = new int[nums.length];
        dp[begin] = nums[begin];
        for (int i = begin + 1; i <= end; i++) {
            dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
        }
        return dp[end];
    }
}
